package com.mgq.algorithm.dp;

/**
 *一个完整的括号字符串定义规则如下:
 * ①空字符串是完整的。
 * ②如果s是完整的字符串，那么(s)也是完整的。
 * ③如果s和t是完整的字符串,将它们连接起来形成的st也是完整的。
 * 例如，"(() ())"，""和"(()) ()"是完整的括号字符串，"())("， "()(”和")"
 * 是不完整的括号字符串。
 * 牛牛有一个括号字符串s,现在需要在其中任意位置尽量少地添加括号,将其转化
 * 为一个完整的括号字符串。请问牛牛至少需要添加多少个括号。
 */
public class MiniBracket {

    public static int bracket(String str) {
        if ("".equals(str)) return 0;
        char[] chars = str.toCharArray();
        int count=0;
        int answer=0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') {
                count++;
            } else {
                count--;
            }
            //如果count =-1,就说明需要一个右括号
            if (count ==-1) {
                answer++;
                count = 0;
            }
        }
        //表示是有几个左括号,需要加上answer
        if (count != 0) {
            return count + answer;
        }
        return answer;
    }

    public static int bracket2(String str) {
        if ("".equals(str)) return 0;
        char[] chars = str.toCharArray();
        int count=0;
        int answer=0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') {
                count++;
            } else {
                if (count == 0) {
                    //count==0了,又是右括号,直接+1个左括号
                    answer++;
                } else {
                    count--;
                }
            }
        }
            return count + answer;
    }

    public static void main(String[] args) {
        String s1 = "((((";
        String s2 = "(((()";
        String s3 = "()()(";
        String s4 = "()()())";
        String s5 = "()()()";
        System.out.println(bracket(s1)==bracket2(s1));
        System.out.println(bracket(s2)==bracket2(s2));
        System.out.println(bracket(s3)==bracket2(s3));
        System.out.println(bracket(s4)==bracket2(s4));
        System.out.println(bracket(s5)==bracket2(s5));
    }
}
